package com.demo.jzoffer2;

import org.junit.Test;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0322_01 {

    /**
     * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
     *
     * 输入: [7,1,5,3,6,4]
     * 输出: 5
     * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
     *
     * 输入: [7,6,4,3,1]
     * 输出: 0
     * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     *
     * 解题思路：设共有n天，第a天买，第b天买，则需要保证 a < b 可以推出交易方案有
     * (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2
     * 暴力法时间复杂度为 n2  考虑使用动态规划来降低时间复杂度
     *
     * 动态规划解析：
     * 1、状态定义：设动态规划列表 dp dp[i] 代表以 price[i] 为结尾的子数组的最大利润（以下简称为前i日的最大利润）
     * 2、转移方程：由于题目限定 买卖股票一次，因此前i日的最大利润 dp[i] 等于 前i-1 日的最大利润dp[i-1] 和 第i日
     * 卖出的最大利润中的最大值
     * 前i日的最大利润 = max(（前i-1）日最大利润 , 第i日价格 - 前i日的最低价格 )
     * dp[i] = (dp[i-1],price[i]-min(price[0:i]))
     * 初始状态: dp[0] = 0,即首日利润为0;
     * 返回值：dp[n-1] 其中 n为dp列表的长度 n-1 代表 第n个元素的下标
     *
     * 效率优化：
     * 时间复杂度降低：前id日的最低价格为 min(price[0:i] 时间复杂度为 O(i) 而在遍历 prices时，可以借助一个变量
     * (记为成本 cost) 每日更新最低价格
     * dp[i] = (dp[i-1],price[i]-min(cost , prices[i])
     * 空间复杂度降低：由于 dp[i] 只与 dp[i-1] ,price[i],cost 有关，因此可以使用一个变量(记为利润 profit) 来代替dp列表
     * profit = (profit,price[i]-min(cost , prices[i]))
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE;
        int profit = 0;//  dp[0] = 0,即首日利润为0;
        for (int i = 0; i < prices.length; i++) {
            cost = Math.min(cost,prices[i]);
//            这个代码这样写相当于允许当天买入，当天卖出了
            profit = Math.max(profit,prices[i] - cost);
        }
        return profit;
    }


    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3() {

    }

}
